题目描述

关系

内容

L2-041 插松枝 - 2024天梯赛刷题榜 (pintia.cn)

问题分析

最初思路

1. 看一眼盒子，是空的，当前没有正在创建的松鼠。创建松树，并弹出树枝 20 加入到松树中；
2. 盒子为空，当前有没有创建完的松树 1，那么弹出树枝，25，不合法，加入盒子中；
3. 看一眼盒子，不合法，弹出，15，合法加入松树中；
4. 看一眼盒子，不合法，弹出，18，不合法，盒子未满，加入盒子；
5. 看一眼盒子，不合法，弹出，20，不合法，盒子没满，加入盒子；
6. 看一眼盒子，不合法，弹出，18，不合法，盒子满了，输出树枝，将 18 放回去；
7. 看一眼盒子，当前没有正在创建的松树，创建一个，弹出盒子顶部，20，加入松树 2；
8. 看一眼盒子，18，合法，加入松树 2；
9. 看一眼盒子，25，不合法，弹出一个，18，合法，加入松树 2；
10. 看一眼盒子，25，不合法，弹出一个 8，合法，加入松树；
11. 看一眼盒子，空的，弹出，5，松树满了，输出松树；
12. 看一眼盒子，25，没有松树，创建一个，加入松树 3；
13. 看一眼盒子，空的，弹出 5，加入松树；
14. 看一眼盒子，空的，弹出，没有数可以弹出了，退出过程；

根据上述的过程，我们可以大致模拟出来。大循环的条件是盒子或弹出器不为空。

我们要检查两个东西，一个盒子，一个是弹出器。盒子是合法的情况为盒子不为空，并且 top 元素不大于当前松树的末尾。如果盒子不满足条件，就要看弹出器了。

弹出器的合法条件为如果弹出器还有元素，并且弹出器弹出的元素合法，那么加入，否则，就加入盒子。

我们要么从盒子找元素加入松树，要么从弹出器找元素加入松树。

什么时候构建下一个松树？题目已经给出条件了。

考察这三个数据结构的数据流向即可。

思路分析

执行流程设计

伪代码如下：

stack<int> box;

input

初始化最开始的树枝大小 max_l = 0x3f3f3f3f;

void build(vector tree) {
	while (1) {
		if (box.isfull() && invalid(q)) {
			break;
		} else if (invalid(box) && q.empty()) {
			break;
		} else if (tree.isfull()) break;
		else { // 开始构建
			bool is_box_valid = box.isNotEmpty() && box.top() <= tree.top();
			bool is_q_valid	= q.isNotEmpty() && q.front() <= tree.top();

			if (is_box_valid) {
				tree.add(box.top());
				box.pop();
			} else if (!is_box_valid && is_q_valid) {
				tree.add(q.front());
				q.pop();
			} else if (!is_box_valid && !is_q_valid) {
				box.push(q.front());
				q.pop();
			}
		}
 	}
}

while (推送器里的树枝没有取完 || 盒子不为空) {
	vector tree(1, max_l);

	build_tree(tree);
	
	输出松树;
	
}

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

stack<int> box;
queue<int> q;

const int INF = 0x3f3f3f3f;
int n, m, k;
void build_tree(vector<int> &tree) {
    while (1) {
        bool is_box_valid = box.size() && box.top() <= tree[tree.size() - 1];
        bool is_q_valid = q.size() && q.front() <= tree[tree.size() - 1];
        if (box.size() >= m && !is_q_valid) break;
        if (!is_box_valid && q.empty()) break;
        if (tree.size() >= k + 1) break;
        
        if (is_box_valid) {
            tree.push_back(box.top()); 
            box.pop();
        } else if (!is_box_valid && is_q_valid) {
            tree.push_back(q.front());
            q.pop();
        } else if (!is_box_valid && !is_q_valid) {
            box.push(q.front());
            q.pop();
        }
    }
}

int main() 
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        q.push(x);
    }
    
    while (q.size() || box.size()) {
        vector<int> t(1, INF);
        
        build_tree(t);
        
        for (int i = 1; i < t.size() - 1; i++) {
            cout << t[i] << " ";
        }
        
        cout << t[t.size() - 1] << endl;
    }
    
    return 0;
}